﻿// 3772. 更新线路.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/3775/

给定一个 n
 个点 m
 条边的有向强连通图。

点的编号为 1∼n
，边的长度均为 1
。

给定一条由点 s
 到点 t
 的简单路径 p1,p2,…,pk
，其中 p1=s,pk=t
。

注意，这条路经不一定是从点 s
 到点 t
 的最短路径。

现在，小明要沿着这条路径从点 s
 走到点 t
。

在他的行进过程中，手机上的导航软件将持续为他导航，持续为他提供最短行进线路建议。

当然，他并不一定会采纳这些建议，因为他一定会沿着之前给定的线路行进。

设想一下，在行进中，导航软件的工作过程。

首先，在点 s
 处，导航软件会找到并显示出一条从点 s
 到点 t
 的最短路径。

如果小明的行进线路恰好与软件推荐线路一致，则软件推荐线路将不会发生任何改变。

但是，如果小明在某一点处，行进线路与软件推荐线路发生了分歧，例如，软件推荐前往点 v
，小明却前往了点 w
。

那么，在他到达点 w
 后，软件就会实时更新推荐线路，即找到并显示出一条从点 w
 到点 t
 的最短路径。

导航软件会一直工作到小明到达点 t
 为止，在这一过程中，软件的提供线路可能会经过若干次更新。

例如，给定一个有向强连通图，如下所示：

a.png

给出的简单路径为 [1,2,3,4](s=1,t=4)
。

那么，小明从点 1
 出发，导航软件找到并显示出一条从点 1
 到点 4
 的最短路径，这样的路径只有一条 [1,5,4]
。

小明并未听从软件的建议，坚持到达了点 2
，此时软件推荐线路实时更新，提供出一条点 2
 到点 4
 的最短路径，例如 [2,6,4]
（注意，软件提供的最短路径也有可能是 [2,3,4]
）。

小明还是不听软件的建议，坚持到达了点 3
，此时软件推荐线路再次更新，提供出一条点 3
 到点 4
 的最短路径，即 [3,4]
。

最后，小明沿软件提供路线，到达目的地点 4
，软件完成导航。

总的来看，软件推荐线路发生了两次更新。

值得注意的是，如果软件在第一次更新推荐线路时，给出的最短路径为 [2,3,4]
，则小明将按照推荐线路走到终点，软件将无需再次更新推荐线路。

也就是说，由于软件在推荐最短路径时具有随机性，所以在整个行进过程中，软件更新推荐线路的次数并不确定。

现在，给定有向图和行进路线，请你求出软件更新推荐线路的最小可能次数和最大可能次数。

输入格式
第一行包含两个整数 n
 和 m
。

接下来 m
 行，每行包含两个整数 u,v
，表示存在一条从点 u
 到点 v
 的有向边。

随后一行包含一个整数 k
。

最后一行包含 k
 个整数 p1,p2,…,pk
。

输出格式
一行，空格隔开的两个整数，表示软件更新推荐路线的最小可能次数和最大可能次数。

数据范围
前三个测试点满足 1≤n≤10
。
全部测试点满足 2≤n≤m≤2×105
，1≤u,v≤n
，u≠v
，2≤k≤n
，1≤pi≤n
，pi
 两两不同。
保证输入没有重边，但是可能同时存在端点相同方向不同的两条边，例如 (a,b)
 和 (b,a)
。

输入样例1：
6 9
1 5
5 4
1 2
2 3
3 4
4 1
2 6
6 4
4 2
4
1 2 3 4
输出样例1：
1 2
输入样例2：
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
7
1 2 3 4 5 6 7
输出样例2：
0 0
输入样例3：
8 13
8 7
8 6
7 5
7 4
6 5
6 4
5 3
5 2
4 3
4 2
3 1
2 1
1 8
5
8 7 5 2 1
输出样例3：
0 3
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 